#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>
#include <memory>
using std::cout;
using std::endl;
using std::cin;
using std::vector;

struct Edge {
    int start;
    int end;
    int weight;
    Edge(int s, int e, int w):
        start(s), end(e), weight(w) 
    {}
};

typedef std::unique_ptr<Edge> pEdge;

constexpr int UNKNOWN = INT_MAX;
int V; //顶点总数
int E; //边总数
vector<pEdge> edges;

void BellmanFord(int start) {
    vector<int> distance(V, UNKNOWN);
    distance[start] = 0;
    for (int i = 0; i < V; ++i) {
        for (auto& e : edges) {
            if (distance[e->start] == UNKNOWN)
                continue;
            if (distance[e->start] + e->weight < distance[e->end])
                distance[e->end] = distance[e->start] + e->weight;
        }
    }
    cout << "Distance form vertex:" << start << endl;
    for (int i = 0; i < V; ++i) {
        cout << "\t" << i << ":";
        if (distance[i] == UNKNOWN) {
            cout << "Unvisted;\n";
            continue;
        }
        cout << distance[i] << endl;
    }
}

int main() {
    cin >> V >> E;
    for (int i = 0; i < E; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        edges.emplace_back(new Edge(a, b, w));
    }
    int start;
    cin >> start;
    BellmanFord(start);
    return 0;
}